There are various mechanisms to control access to data within a database system. One is example is a coarser grained approach that bases accesses privilege at the table level. For example, if a user SCOTT has SELECT privilege on JOE.EMP table, then SCOTT can access all the rows of the table.
A finer grained approach may base access privileges at the row level. One such approach associates an Access Control List (“ACL”) at the row-level and uses query rewrite to control access using the row-level association of the ACL. An ACL contains one or more access control entries. Each access control entry grants a set of privileges (e.g. read, write, etc) to a principal, such as a user, user group, or a user role. By associating an ACL with a row, a security policy may be specified at the level of a row.
Under this approach, when a database system receives a query from a user, it rewrites the query (at least logically) to use ACLs to control what may be accessed by the query. Rewriting a query in a way that uses ACLs to control what operations are performed to execute the query, such accessing or modifying particular rows, is referred to herein as an access control rewrite, or simply rewrite.
In an access control rewrite, the query may be rewritten by appending a predicate that invokes an access control function or operator, to determine whether a user may perform a particular operation on a row. The access control function is implemented to determine whether one or more conditions or criteria, referred to herein as access control conditions, are met. If the access control conditions are met, the user has the necessary privilege to perform the required operation on a particular row, and the access control function returns a result indicating so. The following query QB illustrates an access control rewrite and use of an access control function.
QBselect * from Empwhere Salary > 1000;is implicitly rewritten to
QB′Funcselect * from Empwhere Salary > 1000 ANDCHECK_ACL(aclid, “read”) = 1.
The access control function CHECK_ACL takes an ACL identifier (aclid column in this example) and required privileges (e.g. “read”) for the query as arguments. The access control function CHECK_ACL evaluates to 1 or 0, depending on whether the ACL of a row grants the required privilege to the current user.
The predicate that includes the CHECK_ACL function is evaluated using functional evaluation. In functional evaluation, each row of a set of rows is examined to determine whether a row satisfies a particular condition. In this case, the CHECK_ACL predicate (i.e. predicate containing the CHECK_ACL function) is evaluated for each row.
However, in many scenarios, queries rewritten in this way perform poorly. Specifically, if other predicates in the queries are unselective and the CHECK_ACL predicate is selective, then the system evaluates CHECK_ACL for many rows but, because the function is selective, CHECK_ACL eliminates most of the rows from the final query results. Thus the relative high I/O cost of accessing many rows is incurred for a result that includes few of them, leading to overall poor performance.
In the current example, for purposes of illustration, table Emp has 1 million rows. The ACLs are set up such that the user issuing query QB has permission to access only 20 rows. There are 100,000 employees matching the Salary predicate, i.e. having Salary>1000 evaluate to true. To compute the query QB'Func, a database system accesses 100,000 rows (perhaps using an index), applies CHECK_ACL function to all of them, but eliminates all but 20 rows from the result. Clearly, this execution strategy suffers from poor performance, and a better approach is needed.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.